package testsql;

import java.util.ArrayList;
import java.util.List;

public class Q39 {

	public static void main(String[] args) {
		Solution solution = new Q39.Solution();
		int[] candidates = new int[]{2,3,5};
		System.out.println(solution.combinationSum(candidates, 8));
	}
	
	public static class Solution {
		public List<List<Integer>> results = null;
		
	    public List<List<Integer>> combinationSum(int[] candidates, int target) {
	    	results = new ArrayList<>();
	        backTracking(0, candidates, target, 0, new ArrayList<Integer>());
	    	return results;
	    }
	    
	    public void backTracking(int i, int[] candidates, int target, int sum, List<Integer> result){
	    	if(sum == target){
	    		results.add(result);
	    		return;
	    	}
	    	if(sum > target){
	    		return;
	    	}
	    	for(int j = i; j<candidates.length; j++){
	    		int newSum = sum + candidates[j];
	    		List<Integer> newResult = new ArrayList<>();
	    		newResult.addAll(result);
	    		newResult.add(candidates[j]);
	    		backTracking(j, candidates, target, newSum, newResult);
	    	}
	    }
	}

}
